line = "530070000600195000098000060800060003400803001700020006060000280000419005000080079"
line1 = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"

# possible = "123456789"


def makePossible(grid):
    possible = [set("123456789") for i in range(9) for j in range(9)]
    for i in range(9):
        for j in range(9):
            x_line = set([grid[i][j] for j in range(9)])
            y_line = set([grid[i][j] for i in range(9)])
            m = i // 3
            n = j // 3
            square = set([
                grid[i][j] for i in range(3 * m, 3 * m + 3)
                for j in range(3 * n, 3 * n + 3)
            ])
            possible[i*9+j] -= (x_line & y_line & square)

    return possible


def makeGrid(data):
    grid = []
    if '.' in data:
        data = data.replace('.', '0')
    grid = [list(data[i*9:(i+1)*9]) for i in range(9)]
    possible = makePossible(grid)
    return grid, possible


def beauty(promble):
    for i in range(9):
        if i % 3 == 0:
            print("-------------")
        line = ""
        for j in range(9):
            if j % 3 == 0:
                line = line + "|" + str(promble[i][j])
            else:
                line = line + str(promble[i][j])
        print(line + "|")
    print("-------------")


def guess(x, y, s):
    x_line = [promble[x][j] for j in range(9)]
    y_line = [promble[i][y] for i in range(9)]
    m = x // 3
    n = y // 3
    square = [
        promble[i][j] for i in range(3 * m, 3 * m + 3)
        for j in range(3 * n, 3 * n + 3)
    ]

    if s in x_line:
        return False
    if s in y_line:
        return False
    if s in square:
        return False

    return True


def solve():
    for i in range(9):
        for j in range(9):
            if promble[i][j] == '0':
                for s in possible[i*9+j]:
                    if guess(i, j, s):
                        promble[i][j] = s
                        solve()
                        promble[i][j] = '0'
                return

    beauty(promble)


if __name__ == "__main__":
    promble, possible = makeGrid(line1)
    beauty(promble)
    solve()
